% Copyright 2018 Google LLC
%
% Use of this source code is governed by an MIT-style
% license that can be found in the LICENSE file or at
% https://opensource.org/licenses/MIT.

%!TeX spellcheck = en-US

\documentclass[eprint.tex]{subfiles}
\begin{document}
\section{Specification}
\begin{figure}
    \begin{floatrow}
        \ffigbox{
            \subfile{finalfig.tex}
        }{
            \caption{HBSH}\label{finalfig}
        }
        \ffigbox{
            \begin{algorithmic}[0]
                \Procedure{HBSHEncrypt}{$T,P$}
                \State $P_L \Concat P_R \gets P$
                \State $P_M \gets P_R \boxplus H_{K_H}(T, P_L)$
                \State $C_M \gets E_{K_E}(P_M)$
                \State $C_L \gets P_L \oplus S_{K_S}(C_M)[0;\abs{P_L}]$
                \State $C_R \gets C_M \boxminus H_{K_H}(T, C_L)$
                \State $C \gets C_L \Concat C_R$
                \State \textbf{return} $C$
                \EndProcedure
            \end{algorithmic}
            \begin{algorithmic}[0]
                \Procedure{HBSHDecrypt}{$T,C$}
                \State $C_L \Concat C_R \gets C$
                \State $C_M \gets C_R \boxplus H_{K_H}(T, C_L)$
                \State $P_L \gets C_L \oplus S_{K_S}(C_M)[0;\abs{C_L}]$
                \State $P_M \gets E_{K_E}^{-1}(C_M)$
                \State $P_R \gets P_M \boxminus H_{K_H}(T, P_L)$
                \State $P \gets P_L \Concat P_R$
                \State \textbf{return} $P$
                \EndProcedure
            \end{algorithmic}
        }{\caption{Pseudocode for HBSH; $P_R$, $P_M$, $C_M$, $C_R$ are $n$ bits long}\label{pseudocode}}
    \end{floatrow}
\end{figure}

\parintro{Notation}
Partial application is implicit; if we define $f: A \times B \rightarrow C$ and
$a \in A$ then $f_a: B \rightarrow C$, and if $f_a^{-1}$ exists then $f_a^{-1}(f_a(b)) = b$.
\begin{itemize}
    \item $\abs{X}$: length of $X \in \bin^{*}$ in bits
    \item $\lambda$: the empty string $\abs{\lambda} = 0$
    \item $\Concat$: bitstring concatenation
    \item $Y[a;l]$: the subsequence of $Y$ of length $l$ starting at the 0-based index $a$.
    \item $\pad_l(X) = X \Concat 0^v$
    where $v$ is the least integer $\geq 0$ such that $l$ divides $\abs{X} + v$
    \item $\intify: \bin^{*} \rightarrow \ZZ$: the
    standard little-endian map such that
    $\intify(\lambda) = 0$, $\intify(0 \Concat X) = 2\intify(X)$, $\intify(1 \Concat X) = 1 + 2\intify(X)$
    \item $\fromint_l(y) = X$: the unique
    $l$-bit sequence such that $\intify(X) \equiv y \pmod{2^l}$
    \item $n$, $l_S$: parameters which depend on the
    primitives from which HBSH is built;
    for Adiantum and HPolyC, $n = 128$ and $l_S = 2^{73}$
    \item $\mathcal{T}$: the
    space of tweaks, which depends on the hash function used
    \item $\mathcal{M} = \bigcup_{i=n}^{l_S + n}\bin^i$: the
    space of plaintexts and ciphertexts
    \item $\mathcal{L} = \bigcup_{i=0}^{l_S}\bin^i$, $\mathcal{R} = \bin^n$:
    messages are processed in two parts,
    $\mathcal{L} \times \mathcal{R}$
    \item $H: \mathcal{K}_H \times \mathcal{T} \times \mathcal{L} \rightarrow \mathcal{R}$:
    two-argument hash function with keyspace $\mathcal{K}_H$
    \item $\boxplus, \boxminus: \mathcal{R} \times \mathcal{R} \rightarrow \mathcal{R}$:
    group operations
    \item $E: \mathcal{K}_E \times \mathcal{R} \rightarrow \mathcal{R}$:
    $n$-bit block cipher with key space $\mathcal{K}_E$
    \item $S: \mathcal{K}_S \times \mathcal{N} \rightarrow \bin^{l_S}$:
    stream cipher with key space $\mathcal{K}_S$
    and nonce space $\mathcal{N}$
    \item $\HBSH : \mathcal{K}_S \times \mathcal{T} \times \mathcal{M} \rightarrow \mathcal{M}$:
    the HBSH construction takes a key, a tweak, and a plaintext,
    and returns a ciphertext
    such that $\abs{\HBSH_{K_S}(T, M)} = \abs{M}$
\end{itemize}
We map bytes to bitstrings with $\fromint_8$.
Where we have eg $P_L \Concat P_R \gets P$
with $P \in \mathcal{M}$, $P_L, P_R$ is the unique
pair of elements in $\mathcal{L} \times \mathcal{R}$ such that
$P_L \Concat P_R = P$.

\parintro{HBSH}
The HBSH construction is shown in \autoref{finalfig} and \autoref{pseudocode}.
From plaintext $P$ of at least $n$ bits and a tweak $T$,
it generates a ciphertext $C$ of the same length as $P$.
HBSH divides the plaintext into a right-hand part of $n$ bits and a left-hand part with
the remainder of the input, and applies an unbalanced Feistel network.

\parintro{Hash}
$H$
is an $\epsilon$-almost-$\Delta$-universal ($\epsilon$-$\Delta$U) function
(as defined in \autoref{eadudef})
yielding a group element represented as an $n$-bit string.
$\boxplus$ represents addition in a group which depends
on the hash function, and $\boxminus$ subtraction.

\begin{sloppypar}
    Adiantum and HPolyC differ only in their choice of hash function. HPolyC is
    based on Poly1305, while Adiantum uses both Poly1305 and NH;
    specifically little-endian $\NH^T[256, 32, 4]$ with a stride of 2 for fast
    vectorization. In both cases, the group used for $\boxplus$ and $\boxminus$ is
    $\ZZ/2^{128}\ZZ$. The value of $\epsilon$ depends on bounds on the input
    lengths.
    We defer full details to \autoref{hashing}.
\end{sloppypar}

\parintro{Block cipher}
The block cipher $E$
is only invoked once no matter the size of the input, so for disk-sector-sized inputs
its performance isn't critical. Adiantum and HPolyC use AES-256~\cite{AES}, so $n = 128$ and $\mathcal{K}_E = \bin^{256}$.

\parintro{Stream cipher}
$S$
is a stream cipher which takes a key and a nonce and produces a long random stream. In normal use
the nonce is an $n$-bit string, but for key derivation we use the empty string $\lambda$, which
is distinct from all $n$-bit strings; thus $\{\lambda \} \cup \mathcal{R} \subseteq \mathcal{N}$.

Adiantum and HPolyC use the XChaCha12 stream cipher.
The ChaCha~\cite{chacha}
stream ciphers take a 64-bit nonce, and RFC7539~\cite{RFC7539} proposes
a ChaCha20 variant with a 96-bit nonce, but we need a 128-bit nonce.
The XSalsa20 construction~\cite{xsalsa}
proposed for Salsa20~\cite{salsa20,salsa812} extends the nonce to 192 bits, and
applies straightforwardly to ChaCha~\cite{xchacha,monocypher,libsodiumxchacha}.
We then construct a function that takes a variable-length nonce of up to
191 bits by padding with a 1 followed by zeroes:
$S_{K_S}(C_M) = \XChaCha12_{K_S}(\pad_{192}(C_M \Concat 1))$ and
$\mathcal{N} = \bigcup_{i=0}^{191}\bin^i$.
The maximum output length $l_S = 2^{73}$,
and keyspace $\mathcal{K}_S = \bin^{256}$.

\parintro{Key derivation}
HBSH derives $K_E$ and $K_H$ from $K_S$ using a zero-length nonce:
$K_E \Concat K_H \Concat \ldots = S_{K_S}(\lambda)$. An earlier version of this paper
used $K_H \Concat K_E \Concat \ldots = S_{K_S}(\lambda)$ for HPolyC.

A second, functional definition of HBSH is given in \autoref{funcdef}.

\subbib
\end{document}
